package hl.leco;

import java.util.Arrays;

/**
 * 最长 有效括号 的长度
 * @author Liu Huan
 */


public class day_7_4 {

    /**
     * 思路 1 ： 动态规划
     * 定义 dp[i] 表示 以下标 i 字符 结尾的 最长有效括号长度
     * 所以 如果 s[i] == '(' 则 dp[i] == 0
     * 遍历字符串每个字符，如果 s[i] == ')' 则 dp[i] 由三部分组成，
     *                  首先 如果可以确定它的左括号下标（i-dp[i-1]-1），则 2
     *                  其次，加上 内部的有效字串长度 dp[i-1]
     *                  再次，计算 之前的有效字串长度 dp[i-dp[i-1]-2]
     *                          需要确定 之前的 有效字串长度 下标 > -1
     *                  每次跟新 max 值，最后返回
     *
     * @param s 输入的字符串
     * @return 返回字符串中最长 有效括号 的长度
     */
    public static int maxLength(String s) {
        int[] dp = new int[s.length()];
        Arrays.fill(dp, 0);
        int max = 0;
        for (int i = 1; i < s.length(); i++) {
            if(s.charAt(i) == ')' && i-dp[i-1]-1>0 && s.charAt(i-dp[i-1]-1) == '(') {
                dp[i] = 2 + dp[i-1] + (i-dp[i-1]-2>-1 ? dp[i-dp[i-1]-2] : 0);
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }

    public static void main(String[] args) {
        String s = "()(())";
        System.out.println(maxLength(s));
    }
    
}
